class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        dp = [[False for _ in range(len(s)+1)] for _ in range(len(p)+1)]
        dp[-1][-1] = True
        for pi in range(1, len(p), 2):
            if p[pi]=='*':
                dp[pi-1][-1]=True
                dp[pi][-1]=True
            else:
                break
        for pi in range(len(p)):
            for si in range(len(s)):
                if p[pi]=='*':
                    dp[pi][si]=dp[pi-1][si]
                    continue
                if pi+1<len(p) and p[pi+1]=='*':
                    if p[pi]=='.':
                        dp[pi][si] = dp[pi-1][si] or dp[pi][si-1]
                    else:
                        dp[pi][si] = dp[pi-1][si] or (dp[pi][si-1] and p[pi]==s[si])
                    continue
                if p[pi]==s[si] or p[pi]=='.':
                    dp[pi][si] = dp[pi-1][si-1]
        return dp[len(p)-1][len(s)-1]

print(Solution().isMatch("aab", "c*a*b"))